package com.okaixz.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 陈大专
 * @time 2025/8/6 8:26
 * @des
 **/
public class demo1 {
    public static void main(String[] args) {

        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7), new TreeNode(8))), new TreeNode(3));

        inTree(root);
    }

    public static void inTree(TreeNode root){
        Queue<TreeNode> que=new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()){
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = que.poll();
                System.out.print(node.getVal()+"\t");
                if(node.getLeft()!=null){
                    que.offer(node.getLeft());
                }
                if(node.getRight()!=null){
                    que.offer(node.getRight());
                }
            }
            System.out.println();
        }
    }

    public static void inTree2(TreeNode root){
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode current=root;
        TreeNode prePop=null;
        while (current!=null||!stack.isEmpty()){
            if(current!=null){
                stack.push(current);
                current=current.getLeft();
            }else {
                TreeNode pop = stack.peek();
                if(pop.getRight()==null){
                    prePop=stack.pop();
                }else if(pop.getRight()==prePop){
                    prePop=stack.pop();
                }else {
                    current=pop.getRight();
                }
            }
        }
    }

//    public static void inTree2(TreeNode root){
//        LinkedList<TreeNode> stack=new LinkedList<TreeNode>();
//        TreeNode current = root;
//        TreeNode prePop=null;
//        while (current!=null||!stack.isEmpty()){
//
//            if(current!=null){
//                stack.push(current);
//                if(current.getLeft()==null){
//                    System.out.print(current.getVal()+"\t");
//                }
//                current=current.getLeft();
//            }else if(!stack.isEmpty()){
//                TreeNode pop = stack.peek();
//                if(pop.getRight()==null){
////                    System.out.print(pop.getVal()+"\t");
//                    prePop=stack.pop();
//                }else if(prePop==pop.getRight()){
//                    prePop=stack.pop();
////                    System.out.print(pop.getVal()+"\t");
//                }else {
//                    System.out.print(pop.getVal()+"\t");
//                    current=pop.getRight();
//                }
//
//            }
//
//
//        }
//    }
//
//
//    public static void inTree1(TreeNode root){
//        Queue<TreeNode> queue=new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()){
//            int size = queue.size();
//            for (int i = 0; i < size; i++) {
//                TreeNode node = queue.poll();
//                System.out.print(node.getVal()+"\t");
//                if(node.getLeft()!=null){
//                    queue.offer(node.getLeft());
//                }
//                if(node.getRight()!=null){
//                    queue.offer(node.getRight());
//                }
//            }
//            System.out.println();
//        }
//    }

}
